The present invention relates generally to the generation of routing messages in telecommunications networks.
Telecommunications networks comprise switches interconnected by communication links. A circuit—which may be customer-requested or may be provisioned by the network operator in order to support, for example, switched traffic operations—is established by setting up a path that comprises a sequence of two or more switches and links connecting them. Routing protocols, such as OSPF (Open Shortest Path First), MPLS (Multi-Protocol Label Switching) and PNNI (Private Network to Network Interface), are utilized by the switches to send routing messages among themselves. These routing messages are used to, for example, disseminate network state information throughout the network. So-called signaling messages are communicated among the switches to allocate the bandwidth on particular links in order to provision the circuits, using the disseminated network state information.
The present invention concerns itself with routing messages transmitted among the switches of the network that advertise how much bandwidth remains unassigned on respective links. A message containing such information is referred to herein as an “available bandwidth message.” Upon receipt of a request to provision a new circuit of a certain bandwidth between an originating switch and a terminal switch, the originating switch launches a setup message along a particular path through the network to the destination switch. Bandwidth availability information gleaned from the most recently received available bandwidth messages is used to select a path having sufficient unassigned bandwidth on all of its links to accommodate the requested circuit. As each switch receives the setup message, it allocates the requested amount of bandwidth to the circuit on a link extending to the next switch along the path
A design trade-off is involved in the generation and transmission of available bandwidth messages. It is desirable that they be sent relatively frequently. The greater the time interval between the transmission of available bandwidth messages, the more likely it is that there will be insufficient bandwidth on one or more links identified for a circuit being set up because some or all of the advertised bandwidth may have been allocated to other circuit(s) in the interim. In this case the circuit must be “cranked back” to the originating switch from the point where the attempted allocation has failed, meaning that a crankback message is sent back along the path in question, causing the bandwidth allocated to the circuit to be de-allocated, link-by-link, all the way back to the originating switch. The latter must then identify a different path through the network that (hopefully) does have enough bandwidth on each of its links to accommodate the request, and the process begins again.
As will be appreciated, the necessity of cranking back large numbers of circuits is undesirable in that it represents a waste of network resources and delays fulfillment of the customer's circuit request. The number of crankbanks resulting from attempted circuit setups using outdated available-bandwidth information can be reduced by sending available bandwidth messages more frequently. Indeed, it might be thought that the ideal situation would be to transmit an available bandwidth message for a link whenever the available bandwidth on that link changes. That approach, however, engenders its own problems in that it increases the amount of routing traffic in the network, thereby requiring that the network be designed with enough resources to accommodate the increased traffic level, including the resources needed to formulate the messages, transmit them, and assimilate the information that they contain.
Even if the network has sufficient resources to handle normal circuit setup operations, it could become unduly congested when a large number of circuits need to be set up over a short period of time, such as during a restoration of service after a cable cut or other catastrophic network event has occurred, thereby impairing the network's ability to communicate all kinds of signaling messages needed to carry out the restoration process and thereby impairing the network's ability to rapidly reroute its circuits when such events occur.
The magnitude of the aforementioned problem can be more fully appreciated by considering the way in which available bandwidth messages are transmitted in a system that uses, for example, the above-mentioned PNNI routing protocol. The switches in the network can exist at various levels of the PNNI routing hierarchy. A node in the hierarchy can be a single switch or can be a number of switches assigned to a peer group, wherein each node in the peer group exchanges information with other nodes in the peer group so that all nodes maintain an identical view of the peer group. A so-called peer group leader communicates summary information relating to its own peer group, including the state of its links, to switches outside of the peer group, including to other peer group leaders.
The nodes within a peer group communicate routing information to one another using a type of message referred to as a PNNI Topology State Element, or PTSE. One particular type of PTSE transmitted by a switch is called a link PTSE, which contains information about a particular link. This information includes the amount of bandwidth available on the link. The link PTSE thus functions as the available bandwidth message within the PNNI protocol.
Nodes within a peer group communicate link PTSEs among themselves using a process referred to as “flooding.” Flooding is the reliable hop-by-hop propagation of link PTSEs throughout a peer group to ensure that every node gets every link PTSE. Every node must send its own (self-originated) link PTSEs out on all its interfaces or links from the node. Every node, upon receiving a link PTSE from another node, is expected to send a copy out on all its interfaces or links except, perhaps, the one that goes back to the node from which the link PTSE was received. Some of the switches could have more than fifty links to other neighboring switches (some of which may be in other peer groups), although there may be several parallel links to the same neighbor. Many switches are smart enough to recognize that if there are multiple links to the same neighbor, then they flood available bandwidth messages on only one of these links. Still, the number of neighbors could be large, often greater than fifteen. This means that a switch with an adjacency (number of neighbors) of say, sixteen, could see as many as fifteen duplicates of each link PTSE due to the way flooding works. A duplicate message is discarded but only after a fair amount of processing is done on it. This includes time to process all lower layer encapsulations, as well as the link PTSE message header, and a routing database lookup. This can result in a lot of wasted CPU cycles and can create a high load on the CPU of the switch, often at times (like a large restoration event) when the CPU can least afford wasted cycles. The duplicate messages can also clog queues and result in message discards if the queues fill up.
During a large failure/restoration event, hundreds of links can be affected and the available bandwidth on a link can change rapidly as the failed connections release previously allocated bandwidth and then as restoring connections reassigns available bandwidth. This can result in hundreds, and sometimes thousands, of link PTSEs being flooded to a node in a very short time.
The above problems are ameliorated in the prior art to some extent by imposing certain constraints on how often and under what constraints an available bandwidth message is sent. In particular, prior art arrangements send an available bandwidth message for a link only when the amount of bandwidth available on that link changes (increases or decreases) by a predetermined percentage amount and/or by a predetermined absolute amount. Indeed, by adjusting how great that change needs to be before a message is sent out, the network is able to achieve a workable balance between the timeliness of the bandwidth-availability data and the number of available bandwidth messages launched into the system per unit time. Moreover, the prior art imposes certain time restrictions on the sending of the available bandwidth messages, e.g., the sending by a node or switch of no more than one link PTSE per second for a given link, no matter how many times the available bandwidth of that link changes during that time period.